//package leetcode;
//
//import java.util.HashMap;
//import java.util.Map;
//
//class TreeNode {
//    int val;
//    TreeNode left;
//    TreeNode right;
//
//    public TreeNode(int val) {
//        this.val = val;
//    }
//}
//
//class Node {
//    int val;
//    Node next;
//    Node random;
//
//    public Node(int val) {
//        this.val = val;
//        this.next = null;
//        this.random = null;
//    }
//}
//
//class Solution {
//    Map<Node, Node> cacheNode = new HashMap<Node, Node>();
//
//    public Node copyRandomList(Node head) {
//        if (head == null) {
//            return null;
//        }
//        if (!cacheNode.containsKey(head)) {
//            Node headNew = new Node(head.val);
//            cacheNode.put(head, headNew);
//            headNew.next = copyRandomList(head.next);
//            headNew.random = copyRandomList(head.random);
//        }
//        return cacheNode.get(head);
//    }
//}
//
//public class Test4 {
//}
